package leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode297 {
    public class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null)
                return "";
            Queue<TreeNode> queue = new LinkedList<>();
            StringBuilder string = new StringBuilder();
            queue.add(root);
            TreeNode cur;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur == null)
                    string.append("n,");
                else {
                    string.append(String.valueOf(cur.val) + ",");
                    queue.add(cur.left);
                    queue.add(cur.right);
                }
            }


            return string.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals(""))
                return null;
            String[] split = data.split(",");
            int index = 0;
            TreeNode root = new TreeNode(Integer.valueOf(split[index++])), cur;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            String left, right;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                left = split[index++];
                right = split[index++];
                if (!left.equals("n")) {
                    cur.left = new TreeNode(Integer.parseInt(left));
                    queue.add(cur.left);
                }
                if (!right.equals("n")) {
                    cur.right = new TreeNode(Integer.parseInt(right));
                    queue.add(cur.right);
                }
            }

            return root;
        }
    }
}
